package list;

import array.ArrayFunctions;
import java.util.List;

/**
 * The UnorderedArrayList Class. Same as an ArrayList, but supports O(1) 
 * removal by swapping the element being removed with the last
 * element. Hence the order is not preserved, however it 
 * has an advantage over linked list (which also has O(1) removal as well) in 
 * situations where the order of the elements does not matter by
 * being backed by an array (hence taking advantage of caching and
 * locality of reference).
 *
 * Created: 29-Sep-2012
 * Last Modified: 29-Sep-2012
 * @author Shimu
 */
public class UnorderedArrayList<T> extends IndexableList<T> {

    private static final int INIT_CAPACITY = 10;

    private static final double EXPANSION_FACTOR = 2.0;

    private T[] elements;

    public UnorderedArrayList() {
        super(0);
        this.elements = (T[]) new Object[INIT_CAPACITY];
    }

    @Override
    public boolean add(T element) {
        if (elements.length == size) {
            elements = ArrayFunctions.changeCapacity(elements,
                    EXPANSION_FACTOR);
        }
        elements[size] = element;
        size++;
        return true;
    }

    /**     
     * Throws an IndexOutOfBoundsException if the given index is not
     * within this UnorderedArrayList.
     * @param index  
     * @throws IndexOutOfBoundsException if the given index is not within
     * this UnorderedArrayList.
     */
    private void checkIndex(int index) {
        if (index < 0 || (index > size - 1)) {
            throw new IndexOutOfBoundsException(Integer.toString(index));
        }
    }

    /**
     * Returns the element at the given index.
     * 
     * @param index
     * @throws IndexOutOfBoundsException if the given index is not within
     * this UnorderedArrayList.     
     * @return 
     */
    @Override
    public T get(int index) {
        checkIndex(index);
        return this.elements[index];
    }

    /**
     * Removes the element from the given index. The last element is swapped
     * with the element from the given index. 
     * 
     * @param index
     * @throws IndexOutOfBoundsException if the given index is not within
     * this UnorderedArrayList.
     */
    @Override
    public T remove(int index) {
        checkIndex(index);
        T returnVal = this.get(index);
        ArrayFunctions.swap(elements, index, size - 1);
        size--;
        return returnVal;
    }

    @Override
    public T set(int index, T element) {
        checkIndex(index);
        T returnVal = get(index);
        this.elements[index] = element;
        return returnVal;
    }

    @Override
    public void clear() {
        this.size = 0;
    }

    @Override
    public int size() {
        return this.size;
    }
    
    /**
     * @param index
     * @param element
     * @deprecated 
     */
    @Deprecated
    @Override
    public void add(int index, T element) {
        throw new UnsupportedOperationException();
    }

    @Deprecated
    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}
